package 典型.回溯法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 不允许用同一个位置两次的组合 https://leetcode-cn.com/problems/combination-sum-ii/
public class LC40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(candidates.length==0) return res;
        List<Integer> list = new ArrayList<Integer>();
        Arrays.sort(candidates);
        findList(res,list,candidates,target,0);
        return res;
    }
    public void findList( List<List<Integer>> res,List<Integer> list,int[] candidates, int target,int nums){
        if(target==0) {
            res.add(list);
            return;
        }
        if(target<candidates[0]) return ;
        for(int i =nums;i<candidates.length&&candidates[i]<=target;i++){
            if(i!=nums&&candidates[i]==candidates[i-1]) continue;//注意怎么去重的方法，第一个出现的不去。第二个需要去除
            List<Integer> list1 = new ArrayList<Integer>(list);//注意这里的深拷贝。两次的数组不是同一个数组，所以不能直接用list
            list1.add(candidates[i]);
            findList(res,list1,candidates,target-candidates[i],i+1);
        }
    }

}
